package com.hoppinzq.algorithm.graph;

import com.hoppinzq.algorithm.stackAndQueue.MyQueue;
import com.hoppinzq.algorithm.stackAndQueue.MyStack;

/**
 * 7
 * 深度优先搜索排序 （顶点排序）
 */
public class DepthFirstOrder {
    private boolean[] marked;
    private MyStack<Integer> stack;

    public DepthFirstOrder(MyDigraph myDigraph){
        marked=new boolean[myDigraph.V()];
        stack=new MyStack<>();
        for(int v=0;v< myDigraph.V();v++){
            if(!marked[v]){
                dfs(myDigraph,v);
            }
        }
    }

    private void dfs(MyDigraph myDigraph,int v){
        marked[v]=true;
        MyQueue<Integer> queue=myDigraph.getQueue(v);
        for(Integer i:queue){
            if(!marked[i]){
                dfs(myDigraph,i);
            }
        }
        stack.push(v);
    }

    public MyStack getOrder(){
        return stack;
    }
}
